package leetcode;

/**
 * @author caifangyi
 * @date 2022/8/10
 */

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 640. 求解方程
 * 
 * 求解一个给定的方程，将x以字符串 "x=#value"的形式返回。该方程仅包含 '+' ， '-' 操作，变量x和其对应系数。
 *
 * 如果方程没有解，请返回"No solution"。如果方程有无限解，则返回 “Infinite solutions” 。
 *
 * 如果方程中只有一个解，要保证返回值 'x'是一个整数。
 *
 * 
 *
 * 示例 1：
 *
 * 输入: equation = "x+5-3+x=6+x-2"
 * 输出: "x=2"
 * 示例 2:
 *
 * 输入: equation = "x=x"
 * 输出: "Infinite solutions"
 * 示例 3:
 *
 * 输入: equation = "2x=x"
 * 输出: "x=0"
 * 
 *
 *
 * 提示:
 *
 * 3 <= equation.length <= 1000
 * equation只有一个'='.
 * equation方程由整数组成，其绝对值在[0, 100]范围内，不含前导零和变量 'x' 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/solve-the-equation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Day0640 {
    public static void main(String[] args) {

        Solution solution = new Solution();
        String s = solution.solveEquation("x+5-3+x=6+x-2");
        System.out.println(s+":"+s.equals("x=2"));
        String s2 = solution.solveEquation("x=x");
        System.out.println(s2+":"+s2.equals("Infinite solutions"));
        String s3 = solution.solveEquation("2x=x");
        System.out.println(s3+":"+s3.equals("x=0"));
        String s4 = solution.solveEquation("2x+3x-6x=x+2");
        System.out.println(s4+":"+s4.equals("x=-1"));
        String s5 = solution.solveEquation("x=x+2");
        System.out.println(s5+":"+s5.equals("No solution"));
        String s6 = solution.solveEquation("3x=33+22+11");
        System.out.println(s6+":"+s6.equals("x=22"));
        String s7 = solution.solveEquation("-x=-1");
        System.out.println(s7+":"+s7.equals("x=1"));
        String s8 = solution.solveEquation("x=100");
        System.out.println(s8+":"+s8.equals("x=100"));

    }

    static class Solution {
        public String solveEquation(String equation) {

            String[] split = equation.split("=");
            String left = split[0];
            String right = split[1];

            int[] leftInts = extracted(left);
            int[] rightInts = extracted(right);
            Integer xNum = leftInts[0] - rightInts[0];
            if(xNum==0){
                return rightInts[1] - leftInts[1]==0?"Infinite solutions":"No solution";
            }
            Integer num = (rightInts[1] - leftInts[1])/xNum;
            return "x="+num;
        }

        private int[] extracted(String str) {
            Deque<Integer> operationDeque = new ArrayDeque<>();
            Deque<Integer> numDeque = new ArrayDeque<>();
            Deque<Integer> numTempDeque = new ArrayDeque<>();

            Integer xNum = 0;
            Integer num = 0;
            for (int i = 0; i < str.length(); i++) {
                char indexChar = str.charAt(i);
                boolean isOperation = indexChar == '+' || indexChar == '-';
                if(isOperation){
                    int lastNum = getLastNum(operationDeque.isEmpty()?1:operationDeque.pollFirst(), numTempDeque);
                    numDeque.push(lastNum);
                    operationDeque.push(indexChar=='+'?1:-1);
                }

                boolean isDigit = Character.isDigit(indexChar);
                if(isDigit){
                    numTempDeque.push((indexChar-'0'));
                }

                boolean isX = indexChar == 'x';
                if(isX){
                    int opera = operationDeque.isEmpty() ? 1 : operationDeque.pollFirst();
                    boolean empty = numTempDeque.isEmpty();
                    if(!empty){
                        xNum += getLastNum(opera, numTempDeque);
                    }else{
                        xNum += opera;
                    }
                }
            }
            int lastNum = getLastNum(operationDeque.isEmpty() ? 1 :operationDeque.pollFirst(), numTempDeque);
            numDeque.push(lastNum);
            while (!numDeque.isEmpty()){
                num+=numDeque.pollFirst();
            }
            return new int[]{xNum, num};
        }

        private int getLastNum(int opera, Deque<Integer> numTempDeque) {
            int lastNum = 0;
            while (!numTempDeque.isEmpty()){
                lastNum = lastNum*10+ numTempDeque.pollLast();
            }

            lastNum *= opera;

            return lastNum;
        }
    }
}
